package com.zjsru.oneday202208;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/9/3
 * 最长数对链
 * 输入：[[1,2], [2,3], [3,4]]
 * 输出：2
 * 解释：最长的数对链是 [1,2] -> [3,4]
 */
public class FindLongestChain {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs,(a,b)->a[0]-b[0]);
        int n = pairs.length,ans = 1;
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = i - 1; j >=0 && f[i] == 1; j--) {
                if(pairs[j][1] < pairs[i][0]){
                    f[i] = f[j] + 1;
                }
            }
            ans = Math.max(ans,f[i]);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        FindLongestChain findLongestChain = new FindLongestChain();
        int[][] pairs = new int[][]{{1,2}, {2,3}, {3,4}};
        System.out.println(findLongestChain.findLongestChain(pairs));
    }
}
